class Solution
{
public:
    // 剪掉了很多枝的遍历，能过
    int subarrayGCD(vector<int> &nums, int k)
    {
        int n = nums.size();
        int count = 0;
        for (int i = 0; i < n; ++i)
        {
            int _gcd = nums[i];
            int j = i;
            while (j < n)
            {
                _gcd = gcd(_gcd, nums[j]);
                if (_gcd < k || _gcd % k != 0)
                {
                    break;
                }
                if (_gcd == k)
                {
                    ++count;
                }
                ++j;
            }
        }
        return count;
    }

    // 完全暴力，超时
    int subarrayGCD(vector<int> &nums, int k)
    {
        int n = nums.size();
        int count = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j <= i; ++j)
            {
                int _gcd = nums[j];
                for (int l = j + 1; l <= i; ++l)
                {
                    _gcd = gcd(_gcd, nums[l]);
                }
                if (_gcd == k)
                {
                    ++count;
                }
            }
        }
        return count;
    }
};